package com.example.Arithmetic.Arithmetic;

import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.Random;

/**
 * 日期：2023/12/27
 * 时间：10:49
 * 描述：快速排序
 * 单边循环（lomuto分区）要点
 * 选择最右侧元素作为基准点
 * j 找比基准点小的，i 找比基准点大的，一旦找到，二者进行交换
 * 交换时机：j 找到小的，且与 i 不相等
 * i 找到 >= 基准点元素后，不应自增
 * 最后基准点与 i 交换，i 即为基准点最终索引
 */
public class QuickSortLomuto {
    public void sort(int[] ints) {
        quick(ints, 0, ints.length - 1);
    }

    private void quick(int[] ints, int left, int right) {
        if (left >= right) {
            return;
        }
        int i = partition(ints, left, right);
        quick(ints, left, i - 1);
        quick(ints, i + 1, right);
    }

    //    j 找比基准点小的，i 找比基准点大的，一旦找到，二者进行交换
    private int partition(int[] ints, int left, int right) {
        int p = ints[right];
        int j = left;
        int i = left;
        while (j < right) {
//            j小于，所以i不可能更大，执行i++
            if (ints[j] < p) {
                if (i != j) {
                    swap(ints, i, j);
                }
                i++;
            }
            j++;
        }
        swap(ints, i, right);
        return i;
    }

    public void swap(int[] array, int i, int j) {
        int t = array[i];
        array[i] = array[j];
        array[j] = t;
    }

    @Test
    public void test() {
        int[] a = new int[1000000];
        int i = 0;
        Random random = new Random();
        while (i < 1000000) {
            int i1 = random.nextInt(1000);
            a[i] = i1;
            i++;
        }
        System.out.println(Arrays.toString(a));
        QuickSortLomuto quickSort = new QuickSortLomuto();
        quickSort.sort(a);
        System.out.println(Arrays.toString(a));
    }
}
